package 算法.leetcode.offer;

import 算法.leetcode.offer.base.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lchenglong
 * @date 2022/3/19
 */
public class Offer68_I {

    public static void main(String[] args) {
        // [6,2,8,0,4,7,9,null,null,3,5]
        //2
        //4
        List<Integer> list = new ArrayList<Integer>();
        list.add(6);
        list.add(2);
        list.add(8);
        list.add(0);
        list.add(4);
        list.add(7);
        list.add(9);
        list.add(null);
        list.add(null);
        list.add(3);
        list.add(5);
        TreeNode root = TreeNode.init(list);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(4);

        Offer68_I instance = new Offer68_I();
        TreeNode treeNode = instance.lowestCommonAncestor(root, left, right);
        System.out.println(treeNode.val);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归
        if (root == null)return null;
        else if (root.val<p.val&&root.val<q.val)
            return lowestCommonAncestor(root.right,p,q);
        else if (root.val>p.val&&root.val>q.val)
            return lowestCommonAncestor(root.left,p,q);
        else return root;
//        TreeNode ans = root;
//        while (true){
//            if (ans.val<p.val&&ans.val<q.val)
//                ans = ans.right;
//            else if (ans.val>p.val&&ans.val>q.val)
//                ans = ans.left;
//            else break;
//        }
//        return ans;
    }
}
